package com.tgy.leetcode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.stream.Collectors;

/**
 * @Author: tgy
 * @Date: 12/5/20 11:22 AM
 *
 * https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
 */
public class _297_二叉树的序列化与反序列化_01 {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {

        if (root == null) {

            return "[]";
        }

        StringBuilder sb = new StringBuilder("[");

//        traversalTree(root,sb);
//        postTraversalTree(root,sb);
//        inordeTraversalTree(root,sb);
        levelTraversalTree(root,sb);
        if (sb.charAt(sb.length() - 1) == ',') {

            sb.deleteCharAt(sb.length() - 1);
        }

        sb.append("]");
        return sb.toString();
    }

    private void traversalTree(TreeNode node,StringBuilder sb) {

        if (node == null) {

            sb.append("null,");
            return;
        }else {

            sb.append(node.val).append(",");
        }

        traversalTree(node.left,sb);
        traversalTree(node.right,sb);
    }

    private void postTraversalTree(TreeNode node,StringBuilder sb) {

        if (node == null) {

            sb.append("null,");
            return;
        }

        postTraversalTree(node.left,sb);
        postTraversalTree(node.right,sb);
        sb.append(node.val).append(",");
    }

    private void inordeTraversalTree(TreeNode node,StringBuilder sb) {


        if (node == null) {

            sb.append("null,");
            return;
        }

        inordeTraversalTree(node.left,sb);
        sb.append(node.val).append(",");
        inordeTraversalTree(node.right,sb);
    }

    private void levelTraversalTree(TreeNode node,StringBuilder sb) {

        if (node == null) {
            return;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node);

        while (!queue.isEmpty()) {

            TreeNode nd = queue.poll();

            if (nd == null) {

                sb.append("null,");
            }else {

                queue.offer(nd.left);
                queue.offer(nd.right);

                sb.append(nd.val).append(",");
            }
        }

    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {

        if (!data.startsWith("[") || !data.endsWith("]")) {

            return null;
        }

        if (data.length() == 2) {

            return null;
        }

        String[] eles = data.substring(1, data.length() - 1).split(",");

        List<String> collect = Arrays.stream(eles).collect(Collectors.toList());

        return levelGeneralTree(collect);
    }

    private TreeNode generalTree(List<String> eles) {

        if (eles.isEmpty()) {

            return null;
        }

        /**
         * 技巧，删除已经遍历的元素
         */
        String ele = eles.remove(0);
        if (ele.equals("null")) {

            return null;
        }

        TreeNode rootNode = new TreeNode(Integer.parseInt(ele));

        rootNode.left = generalTree(eles);
        rootNode.right = generalTree(eles);
        return rootNode;
    }

    private TreeNode postGeneralTree(List<String> eles) {

        if (eles.isEmpty()) {

            return null;
        }


        /**
         * 技巧，删除已经遍历的元素最后一个元素
         */
        String ele = eles.remove(eles.size() - 1);

        if (ele.equals("null")) {

            return null;
        }

        TreeNode rootNode = new TreeNode(Integer.valueOf(ele));
        rootNode.right = postGeneralTree(eles);
        rootNode.left = postGeneralTree(eles);

        return rootNode;
    }

    private TreeNode inordeGeneralTree(List<String> eles) {

        return null;
    }

    private TreeNode levelGeneralTree(List<String> eles) {

        if (eles.isEmpty()) {

            return null;
        }

        TreeNode root = new TreeNode(Integer.valueOf(eles.remove(0)));

        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        while (!queue.isEmpty()) {

            TreeNode node = queue.poll();

            if (eles.isEmpty()) {

                break;
            }

            String ele = eles.remove(0);
            if (!ele.equals("null")) {

                node.left = new TreeNode(Integer.valueOf(ele));
                queue.offer(node.left);
            }

            if (eles.isEmpty()) {

                break;
            }

            ele = eles.remove(0);
            if (!ele.equals("null")) {

                node.right = new TreeNode(Integer.valueOf(ele));
                queue.offer(node.right);
            }
        }

        return root;
    }
}
